package primary.array;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author Elephas
 * @Date 2022/1/7
 **/
public class TwoSum {
    public static void main(String[] args) {
        final int[] test01_arg1 = new int[]{2,7,11,15};
        final int test01_arg2 = 9;
        twoSum2(test01_arg1,test01_arg2);
    }

    /*
        解法一：对于每num[i]，检查target-nums[i]是否在数组中,时间复杂度o(n2)
     */
    public static int[] twoSum(int[] nums,int target){
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length ; j++) {
                if(i != j && target-nums[i] == nums[j]){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{-1,-1};//没找到
    }

    /*
        解法二：利用一个哈希表
     */
    public static int[] twoSum2(int[] nums,int target){
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(target-nums[i])){
                for (int j = 0; j < nums.length; j++) {
                    if(i!=j && nums[j]==target-nums[i])
                        return new int[]{i,j};
                }
            }
        }
        return new int[]{-1,-1};//没找到
    }
}
